package problem446;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

//446.等差数列划分2-子序列
//https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        HashMap<Long, List<Integer>> hash = new HashMap<>();
        for(int i = 0; i<n; i++) {
            if(hash.containsKey((long)nums[i])) {
                hash.get((long)nums[i]).add(i);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                hash.put((long)nums[i], list);
            }
        }

        int sum = 0;
        for(int j = 2; j<n; j++) {
            for(int i = j-1; i>=0; i--) {
                Long x = 2*(long)nums[i] - (long)nums[j];
                if(hash.containsKey(x)) {
                    List<Integer> list = hash.get(x);
                    for(int k:list) {
                        if(k < i) {
                            dp[i][j] += dp[k][i] + 1;
                        }
                    }

                    sum += dp[i][j];
                }
            }
        }
        return sum;
    }
}

/*
dp[i][j]:以第i和j个数为结尾的等差数列的个数 k i j
*/